#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int minimumMountainRemovals(vector<int> &nums)
    {
        vector<int> dp(nums.size(), 0);
        auto maxIncrease = [&nums, &dp](int n) -> int
        {
            memset(dp.data(), 0, sizeof(int) * nums.size());
            dp[0] = nums[0] < nums[n] ? 1 : 0;
            int maxLength = dp[0];
            for (int i = 1; i < n; i++)
            {
                if (nums[i] >= nums[n])
                    dp[i] = 0;
                else
                {
                    dp[i] = 1;
                    for (int j = 0; j < i; j++)
                    {
                        if (nums[i] > nums[j])
                            dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                maxLength = max(maxLength, dp[i]);
            }
            return maxLength;
        };
        auto maxDecrease = [&nums, &dp](int n) -> int
        {
            memset(dp.data(), 0, sizeof(int) * nums.size());
            dp[nums.size() - 1] = nums[nums.size() - 1] < nums[n] ? 1 : 0;
            int maxLength = dp[nums.size() - 1];
            for (int i = nums.size() - 2; i > n; i--)
            {
                if (nums[i] >= nums[n])
                    dp[i] = 0;
                else
                {
                    dp[i] = 1;
                    for (int j = nums.size() - 1; j > i; j--)
                    {
                        if (nums[i] > nums[j])
                            dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                maxLength = max(maxLength, dp[i]);
            }
            return maxLength;
        };

        int maxLength = 0;
        for (int i = 1; i < nums.size() - 1; i++)
        {
            int i1 = maxIncrease(i);
            int i2 = maxDecrease(i);
            if (i1 != 0 && i2 != 0)
                maxLength = max(maxLength, i1 + i2);
        }
        return nums.size() - maxLength - 1;
    }
};

int main()
{
    cout << "Code1671" << endl;
    Solution s;
    vector<int> nums = {100, 92, 89, 77, 74, 66, 64, 66, 64};
    cout << s.minimumMountainRemovals(nums) << endl;
    return 0;
}